1. The Field of the Invention
The present invention relates to manipulating control data used to generate outlines of graphical objects. More specifically, the present invention relates to dynamically determining directions of freedom for control points used to represent graphical objects such as text.
2. Background and Related Art
Computing technology has transformed the way we work and play. Computing systems now take a wide variety of forms including desktop computers, laptop computers, tablet PCs, Personal Digital Assistants (PDAs), and the like. Even household devices (such as refrigerators, ovens, sewing machines, security systems, and the like) have varying levels of processing capability and thus may be considered computing systems. As time moves forward, processing capability may be incorporated into a number of devices that traditionally did not have processing capability. Accordingly, the diversity of computing systems may likely increase.
Almost all computing systems that interface with human beings use a display to convey information. In many cases, the appeal of the display is considered an important attribute of the computing system. Historically, textual information (e.g., Latin-based characters) was displayed in cells of a Cathode Ray Tube (“CRT”) display device. Each cell was divided into a grid of equally sized grid positions wherein each grid position could be turned on or off. For example, each cell of a CRT could be an 8×8 grid resulting in 64 possible grid positions per cell.
Each character of a character set was stored as a memory image (a bit-map) in the hardware of the CRT display device (e.g., in the video adapter). A memory image included a number of binary values (e.g., 64 binary values for displaying a character on an 8×8 grid), where each binary value corresponded to a specified grid position. One value (e.g., binary “1”) represented that a corresponding grid position was to be “on” when the character was displayed and another value (e.g., a binary “0”) represented that a corresponding grid position was to be “off” when the character was displayed. Upon receiving binary data (e.g., a bit-map) representing a character, the CRT would “turn on” grid positions corresponding to a binary 1 and would “turn off” grid positions corresponding to a binary 0 to display the character.
To somewhat reduce the computing system resources needed to store bit-maps, some operating systems have used proportional bit-maps (e.g., stored on disk) that vary in cell size depending on the character that is to be displayed. For example, in a proportional bit-map character set, the cell for the letter “i” could be more narrow (e.g., width of 3 grid positions or pixels) than the cell for the letter “h” (e.g., width of 6 grid positions or pixels).
However, storing characters as bit-maps (either fixed or proportional) can still consume significant computing system resources. Since a computing system may need to display and print characters of a font (typically 256 or more different characters) at a variety of different sizes, storage of a significant number of different sized bit-maps may be required. For example, it may desirable to have a word processor display and print characters of a font in sizes ranging from 4 pt to 72 pt. Thus, a computing system running the word processor would potentially have to store 68 (72 minus 4) different sizes of bit-maps for displaying the font at different sizes.
Further, since printers typically have different (and for the most part higher) resolution than displays, the computing system would potentially also have to store a corresponding 68 (72 minus 4) different sizes of bit-maps for printing the font at different sizes. For example, a bitmap of an 8×5 grid (requiring 40 bits of storage) may be used to display a character at a specified size, while a bit-map of a 50×30 grid (requiring 1500 bits of storage) is used to print the character at the specified size.
The storage requirement problems associated with bit-map fonts is further compounded when a computing device is to display and print characters from different fonts. That is, the computing device may need to store bit-maps for representing a variety of different fonts at a variety of different sizes. Thus, in the above example, configuring the word processor to use 50 different fonts could result in well over 5,000 different sets of bit-maps (e.g., (68+68)*50). Since many character sets include 256 or more characters, this could easily result over 1 million individual bit-maps (e.g., 5,000*256). Storing bit-maps for underlined, bold, and/or italicized versions of each font can further increase the storage requirements. Further, producing a large number of bitmaps by hand is extremely time consuming.
Accordingly, even more recently, graphics primitives have been used to describe characters of a font. For example, a set of control points and instructions for connecting the points (e.g., connect with a straight line, an arc, a bezier, etc.) can be used to define the outline of a character in an arbitrary grid space (e.g., an arbitrary grid space greater than the highest resolution of a pixelated device). Often, characters will be defined for display at higher resolutions and then mathematically scaled down when the characters are to be rendered at lower resolutions. Thus, only one representation of a character (per font) need be stored.
To scale a character down the location of control points can be divided by a scaling factor. For example, to scale a character down by a scaling factor of 10, the coordinates of each control point defining the character (at the higher resolution) can be divided by 10. It may be that control points defining a character for display on a 100×100 grid are to be scaled down for display on a 10×10 grid. Thus, a control point at grid position (50, 30) can be scaled down to a control point at grid position (5, 3), a control point at grid position (70, 70) can be scaled down to a control point at grid position (7, 7), etc. Accordingly, a smaller outline representing the character may be calculated and there is a reduced need for storing a number of different sizes of bit-maps for the character.
The smaller outline can then be analyzed to identify grid locations that are to be turned on and to identify grid locations that are to be turned off (a process often referred to as “scan conversion”). One scan conversion algorithm determines if the center of a grid position is inside or outside the smaller outline. When the center of a grid position is inside the smaller outline the grid position is turned on. On the other hand, when the center of a grid position is outside the smaller outline the grid position is turned off.
Also, when rendering a character, portions of the character may be required to conform to one or more constraints. A constraint may be expressed as an algorithm defining one or more dependent parameters in terms of one or more independent parameters. Constraints for one control point can be expressed in terms of the location of other control points or locations on a grid (e.g., a capitalization line). For example, the position of a first control point can be expressed in terms of the position of a second control point such that the first control point is a fixed distance from the second control point. Thus, when the second control point is moved, a corresponding move of the first control point may be required so that the first control point conforms to the fixed distance constraint.
Due, in part, to the wide variety of different artistic and technical features in different fonts, constraints are often tailored to individual fonts. To satisfy a constraint, dependent parameters of a control point will often have to give way. Generally, a dependent parameter of a control point will give way in a predetermined direction (which may be referred to as a “freedom vector”). After a control point is moved, the control point can be checked to determine if it still conforms to any constraints placed on the control point. Checking a control point can include taking a scalar measurement in a specified direction (which may be referred to as the “projection vector”). For example, referring back to the above example of a first and second control point, the first control point may need to be moved along a freedom vector until the distance between the first and second control points, measured along a corresponding projection vector, equals the fixed distance.
At times, a control point can be subject to more than one constraint. For example, as depicted in FIG. 1, control point 106 is to conform to two constraints. A first constraint indicates that the distance between control point 106 and edge 101 in the direction of projection vector 103 is to equal distance constraint 107. A second constraint indicates that the distance between control point 106 and edge 102 in the direction of projection vector 104 is to equal constraint distance 108. If control point 109 is moved (e.g., to conform with an independent constraint), control point 106 is also required to be moved such that control point 106 still complies with the fist and second constraints. Typically, control point 106 will be moved along freedom vectors that correspond to each of the two constraints.
Accordingly, inappropriate selection of freedom vectors can result in the inability to comply with constraints. For example, if control point 109 is moved in a vertical direction, it would be difficult for control point 106 to comply with distance constraint 107 if the freedom vector corresponding to distance constraint 107 is in a horizontal direction (i.e., parallel to the X-axis).
Further complications can arise when a control point is to comply with a plurality of constraints. For example, when there are two constraints on a control point, a freedom vector corresponding to the second applied constraint must be set in a direction perpendicular to a projection vector corresponding to the first applied constraint. Failure to set the freedom vector corresponding to the second applied constraint perpendicular to the projection vector corresponding to the first applied constraint can result in compliance with the first applied constraint being undone. For example, any movement on the Y-axis subsequent to moving control point 106 to comply with distance constraint 107 would undo the compliance with distance constraint 107. Thus, the freedom vector for distance constraint 108 (when applied after distance constraint 107) would have to be solely in the X direction (or horizontal).
Further, movement along diagonal freedom vectors can result in numerical errors (e.g., due to rounding) in the rendering process. For example, determining a freedom vector for distance constraint 108 prior to determining a freedom vector for distance constraint 107 would result in a diagonal freedom vector (perpendicular to projection vector 104). Moving along a diagonal freedom vector to comply with distance constraint 107 carries an increased risk that X or Y value for the resulting location of control point 106 will include a fractional grid location value.
To implement constraints for a font, character outlines can be supplemented with rules (often referred to as “hints”) expressed in terms of formal languages, such as, for example, TrueType®. For example, the outline of a character can be supplemented with TrueType® instructions that indicate the width of a vertical stroke (e.g., of an ‘H’) is to be a fixed distance. Hinting has typically been a manual process performed by a human typographer. That is, a human typographer views a character subject to a number of constraints and supplements the outline of the character with computer-executable instructions (e.g., TrueType® instructions) that indicate how to render the character in a manner that complies with the one or more constraints. When the character is to be rendered, a computing system processes the computer-executable instructions and renders the character in accordance with the rules implemented in the computer-executable instructions.
Manual hinting is advantageous since a human typographer can typically recognize, by viewing a character, if the character is appropriately rendered. Alternately, the human typographer can perform an iterative process where hints are added, viewed, and changed repeatedly until a desired rendering is obtained. That is, a human typographer can determine when a character does or does not comply with constraints and can change hints until compliance is obtained. For example, a human typographer can identify that the edges of the vertical stroke of a “T” are not parallel and add (or change) hints so that the edges are parallel. However, manual hinting can consume a considerable amount of time. For example, it may take weeks or even months for a trained typographer to hint a single font.
Automated hinting, as performed by a computing system, is difficult to implement since a computing system has no inherent understanding of freedom vectors or how to select freedom vectors that increase the likelihood of complying with constraints. For example, given a set of control points representing a character, a computing system may have no way to determine an appropriate order for applying multiple constraints to a control point. Thus, a computing system may generate freedom vectors that cause compliance with a previously applied constraint to be undone or may generate freedom vectors with a higher likelihood of causing numerical errors (e.g., diagonal freedom vectors). Therefore, what would be advantageous are mechanisms for dynamically determining directions of freedom used to move control points for compliance with constraints.